Анотація
Тема: Передача інформації по каналу з вирішальною зворотним зв'язком.
Дана випускна робота присвячена використанню завадостійких кодів, зокрема, циклічного коду, у якого кодова відстань дорівнює 4.
У роботі викладені етапи та результати розробки програми, що реалізує кодування циклічним кодом (14,9), наводяться аналіз поставленої задачі, хід розробки, результати вирішення. Також розроблені структурна, функціональна і принципова схеми, що реалізують кодування, декодування, виправлення і виявлення помилок циклічним кодом (14,9).
Зміст
Анотація
Введення
1. Постановка завдання
1.1 Аналіз технічного завдання
1.2 Теоретичне введення
1.2.1 Способи передачі інформації по каналах зв'язку
1.2.2 Основні поняття про перешкодозахищеними кодуванні
1.2.3 перешкодозахисних коди. Циклічний код
1.2.4 Методи побудови циклічних кодів
1.2.5 Методи декодування циклічних кодів і виявлення помилок
1.3 Математична модель
1.4 Побудова твірної матриці
1.5 Розрахунок достовірності переданих повідомлень
1.6 Висновки
2. Технічна реалізація кодера, декодера і вирішувачів 47
2.1 Модульна структура кодера і його робота
2.2 Модульна структура декодера і його робота
2.3 Модульна структура вирішувача кодера і його робота
2.4 Модульна структура вирішувача декодера і його робота
2.5 Вибір мікросхем для реалізації кодера, декодера і вирішувачів
2.6 Опис функціональної схеми кодера і вирішувача кодера
2.7 Опис функціональної схеми декодера і вирішувача декодера
2.8 Опис принципової схеми кодера і вирішувача кодера
2.9 Опис принципової схеми декодера і вирішувача декодера
2.10 Висновки
3. Опис програмних засобів, розроблених в ході реалізації проекту
3.1 Структура системи
3.2 Вхідні дані, форма представлення результатів
3.3 Специфікація на програму в цілому.
3.4 Системні вимоги
3.5 Специфікація на програму в цілому.
4. Результативна частина
4.1 Тестування
4.2 Опис користувальницького інтерфейсу
4.3 Інструкція користувачеві.
4.4 Висновки
5. Висновок
Текст програми на мові VHDL для вирішувача декодера
Документований текст програми
Введення
Діяльність людей пов'язана з переробкою та використанням матеріалів, енергії та інформації. Відповідно розвивалися наукові технічні дисципліни, що відображають питання технології, енергетики та інформатики. Інформаційна техніка є порівняно новою галуззю, яка отримує найбільший розвиток на етапі розробки і застосування електронних обчислювальних машин (ЕОМ) та автоматизованих систем управління (АСУ).
Інформаційна наука тепер знаходить застосування в найрізноманітніших галузях теорії і практики. Центральної гілкою є теорія зв'язку, створена Шенноном на основі теорії ймовірностей.
З передачею та обробкою інформації пов'язані дії будь-якого автоматичного пристрою, поведінка живої істоти, творча діяльність людини, розвиток науки і техніки, економічні та соціальні перетворення в суспільстві і саме життя. Для більш ефективного використання інформації необхідно обмінюватися інформацією, що неможливо без її передачі по каналах зв'язку.
При передачі інформації по каналах зв'язку може відбуватися спотворення переданої інформації. Для запобігання втрат корисної інформації існують різні методи захисту. Одним з них є кодування інформації за допомогою перешкодозахисних кодів.
Двійковий код на всі комбінації не є перешкодозахищеними, так як його комбінації відрізняються один від одного лише в одному розряді, що не дозволяє на приймальній стороні виявити і виправити виникли помилки. У зв'язку з цим виникає необхідність побудови перешкодозахисного коду.
Перешкодозахисних коди - це коди, які дозволяють виявляти і виправляти помилки, тобто коректувати отримані повідомлення. Для досягнення перешкодозахищеності можна ввести надмірність додаванням додаткових контрольних розрядів.
Існує багато різних алгоритмів побудови перешкодозахисних кодів. У даній роботі розглядається код (14,9). Він відноситься до групи циклічних кодів. А саме, він відноситься до циклічних кодами, виявляє 1 і виправляє 1 помилку.
Циклічні коди є основним класом групових завадостійких кодів і використовуються для виправлення і виявлення помилок, що виникають при передачі інформації по каналу зв'язку. Пристрої, які виявляють і виправляють помилки, побудовані на основі циклічного коду, часто застосовуються в різних інформаційних системах.
1. Постановка завдання
1.1 Аналіз технічного завдання
Відповідно до технічного завдання потрібно побудувати математичну модель циклічного коду з кодовою відстанню 4, для кількості букв алфавіту повідомлень 256. Потрібно розрахувати довжину коду і його коригуючу здатність, знайти творчу матрицю коду.
Розробити програму, що реалізовує кодування і декодування розробленим кодом.
Реалізувати схему для його кодування і декодування на рівні функціональної та принципової схеми.
Також необхідно визначити функції вирішувачів, включених в канал зворотного зв'язку, розробити функціональну і принципову схему вирішувачів.
Розрахунково-пояснювальна записка містить:
Введення;
Зміст;.
Постановочну частину;
2. Розробку схеми кодує, декодуючого і обчислювальних пристроїв;
3.Описание розробленої програми;
4.Результатівную частина;
5.Висновок і висновок;
6.Список літератури;
7.Пріложенія;
У записці містяться такі програми:
Структурну схему передачі даних з РІС;
Функціональна схема кодера і вирішувача кодера;
Функціональна схема декодера і вирішувача декодера;
Принципова схема кодера і вирішувача кодера
Перелік елементів;
Принципова декодера і вирішувача декодера;
Перелік елементів;
Документований текст програми вирішувача декодера;
Тимчасові діаграми;
Документований текст програми;
Екранні форми;
Технічне завдання
1.2 Теоретичне введення
1.2.1 Способи передачі інформації по каналах зв'язку
Передача інформації з повторенням (накопиченням). Такий метод передачі застосовують для підвищення достовірності при відсутності зворотного каналу, хоча немає принципових обмежень для його використання і за наявності зворотного зв'язку. Іноді такий метод класифікують як отримання повідомлень з накопиченням. Суть методу полягає в передачі одного і того ж повідомлення кілька разів, запам'ятовуванні прийнятих повідомлень, порівнянні їх поелементно і складанні повідомлення, включаючи елементи, вибрані «по більшості». Припустимо, що тричі передана одна і та ж кодова комбінація 1010101. У всіх трьох передачах вона піддалася впливу перешкод і була перекручена:
1000100
1111101
1010001
1010101
Приймач поразрядно порівнює три прийнятих символу і проставляє ті символи (під рискою), кількість яких в даному розряді переважає.
Існує й інший метод передачі інформації з накопиченням, при якому проводиться не посимвольної порівняння, а порівняння всієї комбінації в цілому. Цей метод простіший реалізується, але забезпечує більш погані результати.
Таким чином, висока завадостійкість методу передачі інформації з повторенням (накопиченням) заснована на тому, що сигнал і перешкоди в каналі не залежать один від одного і змінюються за різними законами (сигнал періодичний, а завада випадкова), тому що повторюється комбінація в кожній передачі, як правило, буде спотворюватися по-різному. Внаслідок цього на прийомі накопичення, тобто підсумовування сигналу, зростає пропорційно числу повторень, тоді як сума перешкоди зростає за іншим законом. Якщо вважати, що перешкоди і сигнал незалежні, то сумуються середн-ие квадрати і середній квадрат суми зростає пропорційно первойстепені. Тому при n повтореннях відношення сигнал / перешкода збільшується в n разів, причому це відбувається без збільшення потужності сигналу. Однак це досягається за рахунок ускладнення апаратури і зростання часу передачі або смуги частот у випадку, якщо сигнал передається на декількох частотах одночасно в часі. Крім того, при залежних помилках і пачках помилок завадостійкість системи знижується.
Передача інформації зі зворотним зв'язком. Завадостійкість передачі без зворотного зв'язку (ПБОС) забезпечується такими способами: завадостійким кодуванням, передачею з повторенням, одночасною передачею з кількох паралельних каналах. У ПБОС застосовуються зазвичай коди з виправленням помилок, що пов'язано з високою надмірністю і ускладненням апаратури. Передача зі зворотним зв'язком (ПЗЗ) багато в чому усуває ці недоліки, тому що дозволяє застосовувати менш перешкодостійкі коди, які мають, як правило, меншою надмірністю. Зокрема, можна використовувати коди з виявленням помилок. Перевагою зворотного каналу є також можливість контролю працездатності об'єкта, що приймає інформацію.
При ПОС вводять поняття прямого каналу, тобто каналу від передавача до приймача, наприклад передається сигнал команди з пункту управління (ПУ) на контрольований пункт (КП). Зворотним каналом при цьому з'явиться передача повідомлення з КП на ПУ про прийняття сигналу команди, причому по зворотному каналу можуть передаватися як повідомлення тільки про те, що сигнал прийнятий на вході КП (в цьому випадку контролюється лише проходження сигналу по каналу зв'язку), так і відомості про повне виконання команди. Можливий і зворотний зв'язок, що дає відомості про поетапне проходження сигналу команди по тракту прийому.
Розглянемо окремі види передачі зі зворотним зв'язком.
Передача з інформаційної зворотним зв'язком (ІОС). Якщо повідомлення передається у вигляді непомехозащіщенного коду, то в кодує пристрої даний код може бути перетворений в перешкодозахищеність. Проте, оскільки в цьому звичайно немає необхідності, кодує пристрій являє собою регістр для перетворення простого паралельного коду в послідовний. Одночасно c передачею по прямому каналу повідомлення запам'ятовується в накопичувачі на передавачі (рис.1.1). На контрольованому пункті прийняте повідомлення декодується і також запам'ятовується в накопичувачі. Однак одержувачу повідомлення передається не відразу: спочатку воно надходить через зворотний канал на пункт управління. У схемі порівняння ПУ відбувається порівняння прийнятого повідомлення з переданим. Якщо повідомлення збігаються, то формується сигнал «Підтвердження» і відбувається передача подальших повідомлень (іноді перед посилкою подальшого повідомлення на КП спочатку надсилається сигнал «Підтвердження» про те, що попереднє повідомлення було прийнято вірно і з накопичувача можна передати інформацію одержувачу). При розбіжності повідомлень, що свідчить про помилку, формується сигнал «Стирання». Цей сигнал замикає ключ для припинення передачі чергового повідомлення і посилається на КП для знищення записаного в накопичувачі повідомлення. Після цього з ПУ проводиться повторна передача повідомлення, записаного в накопичувачі.
Рис.1.1. Спосіб передачі інформації з ІОС.
У системах з ИОС провідна роль належить передавальної частини, тому що вона визначає наявність помилки, приймач тільки інформує передавач про те, яке повідомлення їм отримано. Є різні варіанти передачі з ІОС. Так, існують системи з ІОС, у яких передача сигналів відбувається безперервно і припиняється лише при виявленні помилки: передавач посилає сигнал «Стирання» і повторює передачу. Системи з ІОС, в яких по зворотному каналу передається вся інформація, передана на КП, називаються системами з ретрансляційної зворотним зв'язком. У деяких системах з ИОС передається не вся інформація, а тільки деякі характерні відомості про неї (квитанції). Наприклад, по прямому каналу передаються інформаційні, а по зворотному каналу - контрольні символи, які будуть порівнюватися на передавачі з попередньо записаними контрольними символами. Є варіант, у якому після перевірки прийнятого по зворотному каналі повідомлення та виявлення помилки передавач може або повторити його (дублювання повідомлення), або послати додаткову інформацію, необхідну для виправлення (коригувальна інформація). Число повторень може бути обмеженим або необмеженим.
Зворотний канал використовують для того, щоб визначити, чи необхідна повторна передача інформації. У системах з ИОС підвищення достовірності передачі досягається шляхом повторення інформації лише за наявності помилки, тоді як в системах без зворотного зв'язку (при передачі з накопиченням) повторення здійснюється незалежно від спотворення повідомлення. Тому в системах з ИОС надмірність інформації значно менше, ніж в системах з ПБОС: вона мінімальна при відсутності спотворень і збільшується при помилках. У системах з ИОС якість зворотного каналу має бути не гірше якості прямого щоб уникнути спотворень, які можуть збільшити кількість повторень.
Передача з вирішальною зворотним зв'язком (РІС). Передане з передавача по прямому каналу повідомлення приймається на приймачі (ріс.1.1б), де воно запам'ятовується і перевіряється в декодер (декодері). Якщо помилок немає, то з накопичувача повідомлення надходить до одержувача інформації, а через зворотний канал на передавач подається сигнал про продовження подальшої передачі (сигнал продовження). Якщо помилку виявлено, то декодер видає сигнал, стирає інформацію в накопичувачі. Одержувачу повідомлення не надходить, а через зворотний канал на передавач подається сигнал про переспроса чи повторенні передачі (сигнал повторення або переспроса). На передавачі сигнал повторення (іноді званий вирішальним сигналом) виділяється приймачем вирішальних сигналів, а перемикаючий пристрій відключає вхід кодера від джерела інформації і підключає його до накопичувача, що дозволяє повторити передане повідомлення. Повторення повідомлення може відбуватися кілька разів до його правильного прийому.
Ріс.1.1б. Спосіб передачі інформації з РІС.
При передачі з РІС помилка визначається приймачем. Для цього передане повідомлення повинно кодуватися обов'язково перешкодозахищеними кодом, що дозволяє приймачу виділити дозволену комбінацію (повідомлення) з нерозв'язаних. Це означає, що передача з РІС здійснюється з надмірністю. Вірогідність передачі в системах РІС визначається вибором коду і захистом вирішальних сигналів повторення і продовження. Останнє не представляє особливих труднощів, оскільки ці сигнали несуть одну двійкову одиницю інформації і можуть передаватися досить завадостійким кодом.
Системи з РІС, або системи з перепитав, підрозділяють на системи з очікуванням вирішального сигналу і системи з безперервною передачею інформації.
У системах з очікуванням передача нової кодової комбінації або повторення переданої відбувається тільки після надходження на передавач сигналу запиту.
У системах з безперервною передачею відбувається безперервна передача інформації без очікування сигналу запиту. Швидкість передачі при цьому вище, ніж у системах з очікуванням. Проте після виявлення помилки по зворотному каналу посилається сигнал переспроса і за час приходу на передавач з останнього вже буде передано якесь нове повідомлення. Тому системи з безперервною передачею необхідно ускладнювати відповідної блокуванням приймача, щоб він не брав інформацію після виявлення помилки.
Для порівняння ефективності системи без зворотного зв'язку, в якій застосовується код Хеммінга з виправленням однієї помилки, і системи з РІС, що використовує простий код, вводять поняття коефіцієнта ефективності. Цей коефіцієнт враховує зменшення ймовірності помилкового прийому і витрати на його досягнення, виграш в захисті від помилок (у разі застосування зазначених кодів), відносне зниження швидкості передачі і схемну надмірність, пов'язані з використанням різних кодів. Підсумкове порівняння показало, що на відміну від системи без зворотного зв'язку, що використовує складний код, система з РІС дає виграш в 5,1 рази. Висока ефективність систем з РІС забезпечила їх широке поширення.
Порівняльний аналіз достовірності передачі систем з ИОС і РІС, показав, що:
1) системи з ИОС і РІС забезпечують однакову достовірність передачі при однакових сумарних витратах енергії сигналів у прямому і зворотному каналах за умови, що ці канали симетричні і мають однаковий рівень перешкод;
2) системи з ИОС забезпечують більш високу достовірність передачі, ніж Системи з РІС при відносно слабких перешкодах у зворотному каналі на відміну від прямого. При відсутності перешкод в зворотньому каналі системи з ИОС забезпечують безпомилкову передачу повідомлень за основним каналу;
3) при сильних перешкодах у зворотному каналі більше високу достовірність забезпечують системи з РІС;
4) при пачках помилок у прямому і зворотному каналах більш високу достовірність забезпечують системи з ІОС.
1.2.2 Основні поняття про перешкодозахищеними кодуванні
Перешкодозахищеними (або коригуючими) називаються коди, що дозволяють виявити і виправити помилки в кодових комбінаціях. Звідси і поділ цих кодів на дві великі групи: 1) коди з виявленням помилок, 2) коди з виявленням та виправленням помилок.
Принципи виявлення та виправлення помилок кодами добре ілюструються за допомогою геометричних моделей. Будь-n-елементний двійковий код можна представити n-мірним кубом (рис.1.2), в якому кожна вершина відображає кодову комбінацію, а довжина ребра куба відповідає одній одиниці. У такому кубі відстань між вершинами (кодовими комбінаціями) вимірюється мінімальною кількістю ребер, що знаходяться між ними, позначається d і називається кодовою відстанню Хеммінга.
Таким чином, кодова відстань - це мінімальне число елементів, в яких будь-яка кодова комбінація відрізняється від іншої (по всім парам кодових слів). Наприклад, код складається з комбінацій 1011, 1101, 1000 і 1100. Порівнюючи перші дві комбінації, шляхом складання їх за модулем 2 знаходимо, що d = 2. Порівняння першої і третьої комбінацій показує, що і в цьому випадку d = 2. Найбільше значення d = 3 виявляється при порівнянні першої та четвертої комбінацій, а найменше d = 1 - другої і четвертої, третьої та четвертої комбінацій. Таким чином, для даного коду мінімум відстані d min = l.
При n = 1 n-мірний куб перетворюється на пряму завдовжки d = 1, на одному кінці якої розташовується 1, а на іншому - 0. При n = 2 чотири можливі комбінації (N = 2 2 = 4) розташовуються на чотирьох вершинах квадрата. При цьому комбінації 00 і 11, а також 10 і 01 відрізняються один від одного в двох розрядах, тобто d = 2.
Кодова відстань між двома комбінаціями двійкового коду дорівнює числу одиниць, отриманих при додаванні цих комбінацій за модулем 2, наприклад 10 01 = 11 і 00
11 = 11. Таке визначення кодового відстані зручно при великої розрядності кодів. Так, складаючи комбінації
10110101101
10000000010
00110101111,
визначаємо, що кодова відстань між ними d = 7.
При n = 3 вісім кодових комбінацій розміщуються у вершинах тривимірного куба.
Рис.1.2. Геометрична модель двійкових кодів
Тривимірний куб будується так (рис.1.2), що одна з його вершин лежить на початку координат. Кожній вершині куба приписується кодова комбінація за наступним правилом: на i-му місці кодової комбінації ставиться 0, якщо проекція цієї вершини на i-у вісь координат дорівнює нулю, і 1, якщо проекція дорівнює одиниці. Наприклад, потрібно дізнатися, яку слід записати комбінацію у вершині A 6 (рис.1.2). Проектуючи цю вершину на вісь Х 1, отримаємо одиницю. На другому місці комбінації запишеться також 1 (проекція на вісь X 2 дорівнює одиниці). Так як проекція на вісь Х 3 дорівнює нулю (проекція в початок координат), то на третьому місці комбінації запишеться 0. Отже, вся комбінація у вершині A 6 запишеться як 110.
Якщо використовувати всі вісім слів, записаних у вершинах куба, то утворюється двійковий код на всі сполучення. Як було показано, такий код є непомехоустойчівим. Якщо ж зменшити число використаних комбінацій з восьми до чотирьох, то з'явиться можливість виявлення одиночних помилок. Для цього виберемо тільки такі комбінації, які відстоять один від одного на відстань d = 2, наприклад 000, 110, 011 та 101. Решта кодові комбінації не використовуються. Якщо буде прийнята комбінація 100, то очевидно, що при її прийомі сталася одиночна помилка.
Представлені комбінації побудовані за певним правилом, а саме містять парне число одиниць, а прийнята комбінація 100 - непарне. Можна стверджувати, що комбінація 100 утворилася при спотворенні розряду однієї з дозволених комбінацій, але визначити, яка саме комбінація спотворена, неможливо. Тому такі чи подібні їм коди називають кодами з виявленням помилок.
Крім зазначеної групи комбінацій у тому ж тривимірному кубі може бути отримана ще одна група комбінацій з кодовим відстанню d = 2 (111, 001, 010 і 100). У цих кодових комбінаціях непарне число одиниць і кожна з комбінацій можуть бути використані для виявлення помилки, що виникла при передачі, так як при одиночному спотворенні в комбінації буде парне число одиниць. Однак, якщо необхідно отримати код з виявленням одиночної помилки, у передачі може брати участь тільки одна група, тобто чотири комбінації з можливих восьми. В іншому випадку вийде непомехоустойчівий код, в якому будуть зустрічатися комбінації з d = l.
Таким чином, в перешкодозахисних кодах є комбінації дозволені, складені за певним правилом, і заборонені, що не відповідають цьому правилу.
Так, якщо з восьми комбінацій трехразрядного коду утворено чотири комбінації, що дозволяють виявити одиночну помилку (наприклад, 111, 001, 010 і 100), то ці комбінації є дозволеними, а інші чотири (000, 011, 101 і 110) - забороненими, які повинні фіксуватися на прийомі як спотворені. Іноді сукупність дозволених кодових комбінацій, які при заданих можливих спотвореннях не можуть перейти один в одного, називають системою неперехідних сигналів.
Отже, видно, що побудова завадостійкого коду (а код з виявленням помилки є найпростішим типом такого коду) пов'язане з недовикористанням кодових комбінацій, що призводить до так званої надмірності. Надмірність означає, що з вихідних символів можна побудувати більше комбінацій, ніж їх застосовано в даному коді.
Таким чином, встановлено, що зменшення числа використовуваних комбінацій призводить до підвищення завадостійкості коду. Якщо йти далі по цьому шляху і ще більше обмежити число дозволених комбінацій, то можна створити код не тільки з виявленням, але і з виправленням помилки.
Виберемо в тривимірному кубі такі вершини, кодові позначення яких відрізнялися б один від одного на d = 3. Такі вершини розташовані на кінцях просторових діагоналей куба. Їх може бути тільки чотири пари: 000 і 111, 001 і 110, 100 і 011, 010 та 101. Проте з цих чотирьох пар для передачі можна брати тільки одну будь-яку пару, так як більша кількість пар призведе до того, що в передачі будуть використовуватися комбінації, що відрізняються один від одного на d <3.
Код, створений за таким правилом, може виправити одиночну помилку або виявити дві помилки без їх виправлення. Нехай, наприклад, передається код, що складається з комбінацій 001 і 110. На прийомі отримана комбінація 100. Порівняння її з вихідними комбінаціями показує, що від комбінації 110 вона відрізняється в одному (другому) розряді, а від комбінації 001 - у двох розрядах. Якщо вважати, що зроблена одна помилка, то отриману комбінацію 100 необхідно виправити на 110.
Від дозволеної комбінації 001 відрізняються нa d = l комбінації 011, 000 і 101, а від комбінації 110 - комбінації 111, 100 і 010. Вони і є своєрідними комбінаціями-супутниками, які після прийому можна відносити до тієї чи іншої вихідної комбінації.
Коли говорять про виправлення одиночної помилки, вважають, що ймовірність подвійної помилки в каналі зв'язку пренебрежимо мала. Якщо така ймовірність досить велика, то код з d = 3 можна використовувати для виявлення подвійних помилок, але при цьому виправити одиночну помилку він вже не може. Дійсно, якщо в нашому прикладі була прийнята комбінація 100, то не можна стверджувати, що була передана комбінація 110, так як при подвійних помилки це могла бути і спотворена комбінація 001.
Таким чином, подальше підвищення завадостійкості коду пов'язане зі збільшенням кодового відстані d, що призводить до збільшення надмірності (замість восьми комбінацій використовуються тільки дві).
Коригуюча здатність коду залежить від кодового відстані: а) при d = 1 помилка не виявляється, б) при d = 2 виявляються поодинокі помилки в) у разі d = 3 виправляються поодинокі помилки або виявляються подвійні помилки. У загальному випадку
d = r + s + 1,
де d - мінімальне кодова відстань; r - число виявлених помилок; s - число виправляє помилок.
При цьому обов'язковою умовою є r ≥ s. Так, у нашому прикладі d = 3, і якщо r = s = l, то код може виявити одну помилку і виправити її. Якщо r = 2, s = 0, то код може тільки виявити дві помилки. Як випливає з рівняння, для виправлення однієї помилки і виявлення двох помилок необхідно, щоб d = 2 + 1 + 1 = 4. При d = 4 може бути також варіант, коли r = 3, s = 0. Якщо d = 5, то можуть бути три варіанти: r = s = 2; r = 3, s = l; r = 4, s = 0.
Якщо код тільки виявляє помилки, то
d = r + l, тобто r = d - 1.
Якщо код тільки виправляє помилки, то
d = 2 s +1, тобто s = (d - 1) / 2
Отже, геометричні моделі дозволяють просто будувати малоразрядние коригувальні коди. Однак при довжині коду n> 3 геометричною моделлю користуватися важко, так як вона повинна бути багатовимірної. Тому для побудови багаторозрядних завадостійких кодів використовують різні правила і методики, до розгляду яких і перейдемо.
1.2.3 перешкодозахисних коди. Циклічний код
Циклічні коди відносяться до числа блокових систематичних кодів, у яких кожна комбінація кодується самостійно (у вигляді блоку) таким чином, що інформаційні k і контрольні m символи завжди знаходяться на певних місцях.
Можливість виявлення та виправлення практично будь-яких помилок при відносно малій надмірності в порівнянні з іншими кодами, а також простота схемної реалізації апаратури кодування і декодування зробили ці коди широко поширеними.
Теорія циклічних кодів базується на теорії груп і алгебри многочленів над полем Галуа.
Многочлен (поліном), який можна представити у вигляді добутку многочленів нижчих ступенів, називають приводиться (в даному полі), в іншому випадку - непріводімим. Непріводімие многочлени грають роль, подібну з простими числами в теорії чисел. Непріводімие многочлени Р (Х) можна записати у вигляді десяткових або двійкових чисел або у вигляді алгебраїчного многочлена (табл. 1.1).
Таблиця 1.1 Непріводімие многочлени та їх еквіваленти
Р (Х1) = Х +1 → 3 → 11
Р (Х5) = Х5 + Х3 + Х2 + Х +1 → 47 → 101111
Р (Х2) = Х2 + Х +1 → 7 → 111
Р (Х5) = Х5 + Х4 + Х2 + Х +1 → 55 → 110111
Р (Х3) = Х3 + Х +1 → 11 → 1011
Р (Х5) = Х5 + Х4 + Х3 + Х +1 → 59 → 111011
Р (Х3) = Х3 + Х2 + 1 → 13 → 1101
Р (Х5) = Х5 + Х4 + Х3 + Х2 +1 → 61 → 111101
Р (Х4) = Х4 + Х +1 → 19 → 10011
Р (Х6) = Х6 + Х +1 → 67 → 1000011
Р (Х4) = Х4 + Х3 +1 → 25 → 11001
Р (Х7) = Х7 + Х3 +1 → 137 → 10001001
Р (Х4) = Х4 + Х3 + Х2 + Х +1 → 31 → 11111
Р (Х8) = Х8 + Х4 + Х3 + Х2 +1 → 285 → 100011101
Р (Х5) = Х5 + Х2 +1 → 37 → 100101
Р (Х9) = Х9 + Х4 +1 → 1041 → 1000010001
Р (Х5) = Х5 + Х3 +1 → 41 → 101001
Р (Х10) = Х10 + Х3 + 1 → 2057 → 10000001001
У табл. 1.1 вказані всі Непріводімие многочлени до п'ятого ступеня; включно, використовувані для побудови циклічних кодів. Поліноми більш високих ступенів наводяться лише вибірково.
Многочлен в полі двійкових чисел називається непріводімим, якщо він ділиться без залишку тільки на себе або на одиницю; що стосується многочленів, наведених у табл. 1.1, то це визначення справедливе тільки для кінцевого поля двійкових чисел.
В основу циклічного кодування покладено використання неприводимого многочлена Р (Х), який стосовно циклічним кодами називається твірними, генераторним або виробляють многочленом (поліномом).
1.2.4 Методи побудови циклічних кодів
Як інформаційних символів k для побудови циклічних кодів беруть комбінації двійкового коду на всі сполучення. У загальному випадку, якщо задану кодову комбінацію Q (X) помножити на який утворює многочлен Р (Х), вийде циклічний код, що володіє тими чи іншими властивостями, що коректують залежно від вибору Р (Х). Однак у цьому коді контрольні символи m будуть розташовуватися в самих різноманітних місцях кодової комбінації. Такий код не є систематичним, що утрудняє його схемну реалізацію. Ситуацію можна значно спростити, якщо контрольні символи приписати наприкінці коду, тобто після інформаційних символів. Для цієї мети доцільно скористатися наступним методом.
1. Множимо кодову комбінацію G (X), яку ми хочемо закодувати, на Одночлен , Що має ту ж ступінь, що і утворить многочлен Р (Х).
2. Ділимо твір на який утворює многочлен Р (
):
(1.1)
де Q (X) - частка від ділення; R (X) - залишок.
Множачи вираз (1.1) на Р (Х) і переносячи R (X) в іншу частину рівності, згідно з правилами алгебри двійкового поля, тобто без зміни знаку на зворотний, отримуємо
(1.2)
Таким чином, згідно рівності (1.2), циклічний код, тобто закодоване повідомлення F (X), можна утворити двома способами:
1) множенням однієї з комбінацій двійкового коду на всі сполучення [комбінація Q (X) належить до тієї ж групи того ж коду, що і задана комбінація G (X)] на який утворює многочлен Р (Х);
2) множенням заданої кодової комбінації G (X) на Одночлен , Що має ту ж ступінь, що і утворить многочлен Р (Х), з додаванням до цього твору залишку R (X), отриманого після ділення твори
на який утворює многочлен Р (Х).
Приклад 1.1. Потрібно закодувати одну з комбінацій двійкового коду 1101, що відповідає .
Не зупиняючись на виборі утворює многочлена Р (Х), про що буде сказано далі, візьмемо з табл. 1.1 многочлен Р (Х 3) = Х 3 + Х +1 → 11 → 1011.
Множачи G (X) на , Який має третю ступінь, отримаємо
.
Від множення ступінь кожного многочлена підвищилася, що еквівалентно приписування трьох нулів до многочлену, висловленим у двійковій формі.
Розділивши твір на який утворює многочлен
, Згідно (1.1) отримаємо
або в двійковому еквіваленті
Таким чином, в результаті поділу отримуємо приватне Q (X) тією ж мірою, що і G (X):
і залишок:
.
У підсумку комбінація двійкового коду, закодована циклічним кодом, згідно (1.2) набуде вигляду
F (X) = 1111 • 1011 = 1101000 + 001 = 1101001.
Дійсно, множення 1111 • 1011 (перший спосіб) дає той же результат, що і складання 1101000 + 001 (другий спосіб).
Циклічні коди, які виявляють одиночну помилку (d = 2). Код, утворений многочленом Р (Х) = Х +1, виявляє не тільки одиночну помилку, але і будь-яке непарне число помилок.
Припустимо, що необхідно закодувати повідомлення G (Х) = Х 3 + + Х 2 + X +1 → 1101 за допомогою утворює многочлена P (Х) = Х +1 → 11.
Помножимо G (X) на Х m, що еквівалентно додаванню нуля справа, так як m = 1, оскільки Р (Х) має перший ступінь: (Х 3 + Х 2 +1) X = Х 4 + Х 3 + X → 11010 .
Розділивши отриманий вираз на Р (Х), знайдемо, що залишок R (X) = 1. Отже, кодовий многочлен циклічного коду відповідно до рівняння (1.2) буде мати вигляд
F (X) = G (X) Х m + R (X) = Х 4 + Х 3 + X + 1 → 11010 + 1 = 11 011.
Таким чином, в цьому закодованому повідомленні 11011 n = 5, k = 4 і m = 1, тобто інформаційним символом є комбінація 1101, а контрольним - одиниця в молодшому розряді.
Повідомлення, які були кодовані (1101), є однією з 16 комбінацій чотирирозрядний коду. Якщо потрібно передати всі ці повідомлення в закодованому вигляді, то кожне з них слід кодувати так само, як і комбінацію 1101. Однак проробляти додаткові 15 розрахунків (у загальному випадку 2 k розрахунків) немає необхідності. Це можна зробити простіше, шляхом складання твірного (породжує) матриці.
Утворює матриця складається з одиничною транспонованої матриці і матриці доповнень.
Кількість стовпців транспонованої одиничної матриці дорівнює числу інформаційних символів k. Матриця доповнень виходить із залишків від ділення одиниці з нулями на який утворює многочлен Р (Х), виражений в двійковому еквіваленті. Число залишків дорівнює числу інформаційних символів.
Як випливає з результатів ділення одиниці з нулями на Р (Х) = Х +1 → 11, всі залишки виявляються рівними одиниці. Тому утворює матриця має вигляд
Одинична Матриця
транспо доповнень
лося
ва матриця
Чотири кодові комбінації, з яких складається утворює матриця, є першими кодовими комбінаціями циклічного коду. П'ята комбінація нульова, а так як в чотирирозрядний непомехозащіщенном коді всього N = 2 4 = 16 комбінацій, то решта 11 ненульових комбінацій знаходять підсумовуванням за модулем 2 всіляких комбінацій рядків твірної матриці:
5. 000009. 13.
6. 10.
14.
7. 11.
15.
8. 12.
16.
Згрупуємо отримані комбінації наступним чином:
1. | 00011 | 2. | 00101 | 12. | 01111 |
6. | 00110 | 7. | 01010 | 16. | 11110 |
9. | 01100 | 10. | 10100 | 13. | 11101 |
11. | 11000 | 3. | 01001 | 14. | 11011 |
4. | 10001 | 8. | 10010 | 15. | 10111 |
Видно, що в першому стовпці від комбінації до комбінації дві поруч стоять одиниці зрушуються на один символ вліво, у другому стовпці циклічно зсуваються дві одиниці, які не стоять поряд один з одним, а в третьому стовпці відбувається циклічний зсув чотирьох одиниць. Цей циклічний зсув однієї комбінації по відношенню до іншої і визначив назву кодів - циклічні.
Зауважимо, що циклічний зсув є результатом множення кодової комбінації на X. Дійсно, другу комбінацію можна записати як 00101 → Х 2 + 1, сьому - як (Х 2 + 1) Х = X 3 + X → 01010 і т. п. Якщо при множенні на X ступінь стає рівною X m + l, то отриманий результат потрібно розділити на Х +1. Наприклад, якщо комбінацію 10101 → Х 4 + + Х 2 + 1 помножити на X, то отримаємо Х 5 + Х 3 + X. Ділячи отриманий вираз на Х 5 + 1, знайдемо залишок Х 3 + Х + 1 → 01011. Многочлен 01011 і є результатом циклічного зсуву на один розряд вліво многочлена адресою 10101.
Розгляд отриманих комбінацій показує, що всі вони мають парне число одиниць. Дійсно, контрольні символи виявляються рівними одиниці у разі непарній кількості одиниць у вихідній комбінації і нулю при парному числі одиниць. Таким чином, циклічний код з виявленням одиночної помилки є звичайним кодом з парним числом одиниць.
Циклічні коди з d = З. Ці коди можуть виявляти одиночні та подвійні помилки або виявляти і виправляти поодинокі помилки.
1. Вибір кількості контрольних символів. Є два способи вибору числа m. При першому способі виходять з того, що число контрольних символів m = = n - k залежить від числа інформаційних символів, а значить, і від довжини всієї кодової комбінації. Вибір m виробляється, як і для коду Хеммінга, з виправленням одиночної помилки. Умова може бути записано у вигляді
(1.3)
де Е "- знак округлення убік більшого значення.
При другому способі число контрольних символів визначається за емпіричною формулою
m = Е "Iog 2 [(k +1) + E" Iog 2 (k + 1)]. (1.4)
В основу вибору m в останньому виразі покладено значення числа інформаційних розрядів. Це зручно, так як перше, що відомо на початку кодування, - саме число розрядів інформаційних символів. Рівняння (1.4) дає той же результат, що і (1.3).
З (1.3) випливає, що найбільш економічними є коди, для яких l og 2 (n +1) виражається цілим числом, тобто коли довжина кодової комбінації
n = 2 m - 1, (1.5)
де m має бути цілим числом. Так, при k = 11, n = 15 і m = 4 без всяких заокруглень. Але при k = 12, n = 17, так як m = 5 вибрано з округленням у бік більшого значення, що збільшує надмірність коду: у першому випадку І = 4 / 15 = 0,266, у другому І = 5 / 17 = 0,295.
2. Вибір утворює многочлена Р (Х). Ступінь утворює многочлена l не може бути меншою за кількість контрольних символів m. Це означає, що якщо m = 3, то з табл. 1.1 можна вибрати будь-який утворює многочлен Р (Х) починаючи з третього ступеня і вище. Для спрощення технічної реалізації кодування ступінь Р (Х) слід вибирати дорівнює числу m, тобто l = m. Якщо в таблиці є ряд многочленів з цією ступенем, то з них слід вибрати найкоротший. Однак число ненульових членів многочлена Р (Х) не повинно бути менше кодового відстані d.
3. Знаходження елементів додаткової матриці. Додаткову матрицю знаходять шляхом ділення одиниці з нулями на обраний многочлен R (X) і виписування всіх проміжних залишків. При цьому повинні бути дотримані наступні умови:
а) число залишків має дорівнювати числу інформаційних символів k;
б) для додаткової матриці придатні лише залишки з вагою W, не меншим числа виявлених помилок r, тобто в даному випадку не меншим 2 (W ≥ 2); так можна знайти щонайменше двох помилок.
З умов а) і б) визначається кількість нулів, що приписуються до одиниці при розподілі її на многочлен Р (Х);
в) оскільки елементи додаткової матриці є для даної комбінації контрольними символами, то число розрядів додаткової матриці дорівнює числу контрольних символів m. Внаслідок того, що ступінь утворює многочлена вибирають рівною m, число розрядів додаткової матриці одно також ступеня утворює многочлена. Наприклад, якщо m = 3, а залишок дорівнює 11, то він повинен бути записаний як 011. Зі сказаного випливає, що розрядність залишку дорівнює ступеня утворює многочлена.
4. Складання твірної матриці. Беруть транспоновану одиничну матрицю і праворуч приписують до неї елементи додаткової матриці. Приклад складання твірної матриці був даний при розгляді циклічного коду з виявленням одиночної помилки.
5. Знаходження всіх комбінацій циклічного коду даної групи. Це досягається підсумовуванням за модулем 2 всіляких поєднань рядків твірної матриці, як було показано при розгляді циклічного коду з виявленням одиночної помилки.
Приклад 1.2. Утворити циклічний код, що дозволяє виявляти двократні помилки або виправляти одиночну помилку з усіх комбінацій двійкового коду на всі сполучення з числом інформаційних символів k = 4.
По рівнянню (1.4) знаходимо число контрольних символів:
m = Е "Iog 2 [(4 + 1) + E" log 2 (4 + 1)] = Е "Iog 2 (5 + 3) = 3.
З табл.1.1 вибираємо один з утворюють многочленів третього ступеня. Нехай Р (Х) = Х 3 + Х + 1 → 1011. Знаходимо залишки від ділення одиниці з нулями на Р (Х), які відповідно рівні 011, 110, 111, 101. Залишків повинно бути чотири згідно з кількістю інформаційних символів. Виписуючи транспоновану одиничну матрицю і приписуючи до неї праворуч матрицю доповнень у вигляді залишків, отримуємо твірну матрицю
k 4
k 3
k 2
k 1
m 3
m 2
m 1
a 1
0
0
0
1
0
1
1
a 2
0
0
1
0
1
1
0
a 3
0
1
0
0
1
1
1
a 4
1
0
0
0
1
0
1
Так як всі члени одиничної матриці є комбінаціями заданого чотирирозрядний двійкового коду, то чотири комбінації твірної матриці представляють собою чотири комбінації необхідного циклічного коду. Останні 11 комбінацій циклічного коду (починаючи з п'ятої) можуть бути отримані шляхом підсумовування по модулю 2 цих чотирьох комбінацій твірної матриці так, як було зроблено для коду з d = 2:
5.
6.
7.
8.
9.
10.
11.
12.
13.
14
15
Зауважимо, що комбінація 13 була отримана при виводі рівняння (1.2). Якщо скласти комбінації , То отримаємо циклічний код 1011000, в якому контрольними символами є одні нулі. Нульова комбінація може бути також використана: у неї всі символи - нулі.
Як випливає з табл. 1.1, в якості утворить можна було б взяти і многочлен Р (Х) = Х 3 + Х 2 + 1 → 1101. У цьому випадку утворює матриця прийняла б вигляд
a 1 0001101
a 2 0010111
a 3 0100011
a 4 1000110
Многочлен Р (Х) = Х 3 + Х + 1 → 1011 називається зворотним або двоїстим многочленом многочлена Р (Х) = Х 3 + Х 2 + 1 → 1101. Дійсно, порівнюючи записані в двійковій формі вираження обох многочленів, бачимо, що нулі і одиниці в зворотному многочлене розташовані дзеркально щодо основного многочлена, тобто молодший розряд стає старшим. Так, многочлен 1110101 є зворотним многочлену 1010111. Двоїстий многочлен можна записати у вигляді
Р * (Х) = Х n -1 Р (Х -1). (1.6)
У нашому прикладі Р * (Х) = Х 3 (Х -3 + Х -2 + 1) = Х 3 + Х + 1. Використання подвійних многочленів розширює можливості побудови циклічних кодів, тому що якщо Р (Х) - непріводімий многочлен, то і многочлен Р * (Х) також неприводим.
Циклічне кодування можна здійснювати не тільки шляхом складання твірної матриці з транспонованої матриці і матриці доповнення. Той же результат досягається, якщо кожен з членів одиничної транспонованої матриці помножити на який утворює многочлен. Так, якщо утворює многочлен Р (Х) = Х 3 + Х + 1 → 1011, то множення транспонованої одиничної матриці на цей многочлен дасть
0001X1011 = 0001011
0010Х1011 = 0010110
0100X1011 = 0101100
1000X1011 = 1011000
Зауважимо, що, наприклад, множення 0100X1011 еквівалентно 1011X X 100 = 101100. Нуль ліворуч (0101100) приписується для комплектності коду. Результатом множення з'явився циклічний зсув утворює многочлена. Складанням отриманих комбінацій можна утворити ті ж комбінації, що й за допомогою двох попередніх утворюють матриць.
Нами був обраний як вихідного четирехелементний двійковий код на всі сполучення (k = 4), що дозволило утворити 4 лютого = 16 комбінацій циклічного коду. Ці комбінації є дозволеними, так як після кодування розрядність коду через наявність контрольних символів m = 3 збільшилася до n = 7. З 128 комбінацій семіразрядного двійкового коду 112 будуть невирішеними. При цьому порівняння комбінацій, отриманих за допомогою твірної матриці обома многочленами, показує, що з 32 комбінацій збігаються тільки нульові і складені з одних одиниць.
Таким чином, із двійкового коду на всі сполучення (k = 4) були утворені два циклічних коду за допомогою різних утворюють многочленів: Р (X) = 1011 і P (X) = 1101. При цьому, незважаючи на те що в кожному коді комбінації різні, обидва коди цілком правомочні, так як комбінації в кожному з них відрізняються один від одного на кодова відстань d = 3. У той же час порівняння кодів, складених твірної матрицею [многочлен Р (Х) = Х 3 + Х + 1] і множенням транспонованої матриці на той же многочлен, показує повну ідентичність комбінації цих кодів.
Тепер, коли зрозуміла роль утворює многочлена при складанні циклічних кодів, вимальовуються також такі його властивості, які можуть допомогти при вивченні більш складних циклічних кодів.
Перше властивість утворює многочлена полягає в тому, що всі дозволені комбінації діляться на нього без залишку. Це властивість випливає з (1.2), і його можна перевірити, розділивши будь-яку комбінацію коду на який утворює її многочлен. Таким чином, многочлен Р (Х) як би дозволяє утворити або вибрати з більшого числа комбінації, що задовольняють тільки заданому закону побудови коду, тобто дозволені. Тому многочлен Р (Х) і називається утворюючим.
Друга властивість утворює многочлена таке, що на нього ділиться без залишку не тільки дозволена комбінація, що має ступінь n - 1, а й двочлен Х n + 1. У нашому прикладі n = 7. При розподілі числа 10000001 на 1011 виходить приватне 10111 без залишку. Це означає, що утворює многочлен входить в якості співмножники в розклад двочлена Х n + 1, який з урахуванням рівності (1.5) можна записати у вигляді . Так для двочлена
складові співмножники розкладу повинні бути непріводімимі многочленами, ступеня яких є дільниками числа m = 3. До числах, на які m = 3 ділиться без залишку, відносяться 1 і 3. З таблиці. 1.1 випишемо всі Непріводімие многочлени першого та третього ступенів, які і з'являться сомножители в розкладанні двочлена Х 7 +1:
Х 7 +1 = (Х +1) (Х 3 + Х +1) (Х 3 + Х 2 + 1) (1.7)
Один з непріводімих многочленів третього ступеня і повинен бути обраний для кодування, якщо k = 4. Зауважимо, що таке розкладання двочлена Х n +1 є одним з методів вибору утворює многочлена.
У розглянутому прикладі при k = 4 і m = 3 n = k + m = 7. У літературі циклічні коди такого типу називаються кодами (7,4). З прикладу не випливає, що для всіх циклічних кодів з виявленням подвійної помилки утворює многочлен буде завжди мати третю ступінь. Чим більше довжина коду, тим вище ступінь утворює многочлена, що пояснюється збільшенням кількості контрольних символів. Так, при k = 26 згідно рівнянню (1.4) m = 5. Це означає, що ступінь утворює многочлена повинна бути не менше п'ятої. Такий код позначають як код (31,26).
Циклічні коди з d = 4. Ці коди можуть виявляти одиночні, подвійні та потрійні помилки або виявляти подвійні і виправляти поодинокі помилки.
1. Вибір кількості контрольних символів. Число контрольних символів в цьому коді повинно бути на одиницю більше, ніж для коду з d = 3:
(1.8)
Для знаходження можна скористатися рівнянням (1.4). Якщо число контрольних символів визначається, як в коді Хеммінга, то рівняння (1.3) набуде вигляду
(1.9)
2. Вибір утворює многочлена. Створюючий многочлен : Дорівнює добутку двочлена (Х +1) на многочлен
(1.10)
Це пояснюється тим, що двочлен (Х +1) дозволяє виявити всі одиночні і потрійні помилки, а многочлен Р (Х) - подвійні помилки. Так, для коду (7,3), виявляє всі триразові помилки, можна було б вибрати .
У загальному випадку ступінь l многочлена дорівнює числу m. Подальша процедура кодування залишається такою ж, як і при утворенні коду з виявленням подвійної помилки.
Приклад 1.3. Потрібно закодувати повідомлення 10101010101010 циклічним кодом з d = 4:
G (X) = Х 13 + Х 11 + Х 9 + Х 7 + Х 5 + Х 3 + Х → 10101010101010.
Визначаємо число контрольних символів по рівнянню (1.4):
З рівняння (1.8) випливає, що . Вибираємо з табл. 1 .1 утворює многочлен для d = 3. Нехай
. Тоді
Так як необхідно закодувати тільки одне повідомлення G (X), а не весь ансамбль двійкових кодів з k = 14, то будемо дотримуватися процедури кодування, що виконується за рівнянням (1. 2). Вибираємо Одночлен . Тоді
Розділивши отриманий вираз на , Знаходимо залишок:
Отже, передана закодована комбінація буде мати вигляд F (X) = (Х 19 + Х 17 + Х 15 + Х 13 + Х 11 + Х 9 + Х 7) + (Х 4 + Х 3 + Х 2 + X + 1) .
10101010101010 011111
Інформаційні Контрольні
символи символи
1.2.5 Методи декодування циклічних кодів і виявлення помилок
Виявлення помилок. Ідея виявлення помилок у прийнятому циклічному коді полягає в тому, що при відсутності помилок закодована комбінація F (X) ділиться на який утворює многочлен Р (Х) без залишку. При цьому контрольні символи m відкидаються, а інформаційні символи k використовуються за призначенням. Якщо відбулося спотворення прийнятої комбінації, то ця комбінація F (X) перетворюється в комбінацію Н (Х), яку можна представити як суму двох многочленів:
H (X) = F (X) + E (X), (1.11)
де Е (Х)-многочлен помилок, що містить стільки одиниць, скільки елементів у прийнятій комбінація не збігається з елементами переданої комбінації.
Нехай, наприклад, була передана комбінація коду (7,4) == 1101001, закодована за допомогою Р (Х) = 1011. Якщо вона прийнята правильно, то поділ на Р (Х) дасть залишок, що дорівнює нулю. Якщо ж комбінація прийнята як Н (Х) = 1101011, то при діленні на Р (Х) утворюється залишок 010, що свідчить про помилку, і прийнята комбінація бракується.
Виявлення і виправлення помилок. Існує кілька варіантів декодування циклічних кодів. Один з них полягає в наступному.
1. Обчислення залишку (синдрому). Так само як і в кодах з виявленням помилок, прийняту комбінацію ділять на який утворює многочлен Р (Х). Залишок R (X) = 0 означає, що комбінація прийнята без помилок. Наявність залишку свідчить про те, що комбінація прийнята перекрученою. Подальша процедура виправлення помилок протікає таким чином.
2. Підрахунок ваги залишку W. Якщо вага залишку дорівнює або менше числа виправляє помилок, тобто , То прийняту комбінацію складають по модулю 2 із залишком і отримують виправлену комбінацію.
3. Циклічний зсув на один символ вліво. Якщо W> s, то роблять циклічний зсув на один символ вліво і отриману комбінацію знову ділять на який утворює многочлен. Якщо вага отриманого залишку , То циклічно зрушену комбінацію складають із залишком і потім циклічно зрушують їх у зворотний бік вправо на один символ (повертають на попереднє місце). У результаті отримують виправлену комбінацію.
4. Додаткові циклічні зрушення вліво. Якщо після циклічного зсуву на один символ, як і раніше W> s, то роблять додаткові циклічні зрушення вліво. При цьому після кожного зсуву зрушену комбінацію ділять на Р (Х) і перевіряють вагу залишку. При виконують дії, зазначені у п. 3, з тією лише різницею, що зворотних циклічних зрушень вправо роблять стільки, скільки їх було зроблено вліво.
Приклад 1.4. Прийнято код 1101110, закодований утворюючим многочленом Р (Х) = 1011 і з s = l. Перевірити наявність помилки і в разі виявлення виправити її.
Ділимо комбінацію 1101110 на 1011 і знаходимо, що залишок R (X) = 111. Так як це не задовольняє рівності W = s, зрушуємо комбінацію 1101110 циклічно на один символ вліво. Отримуємо 1011101. У результаті ділення цієї комбінації на Р (Х) знаходимо залишок R 1 (X) = 101. Вага цього залишку дорівнює двом, тобто більше s. Здійснюємо новий циклічний зсув вліво. Отримуємо 0111011. Поділ на Р (Х) дає залишок R 2 (X) = 001, вага якого дорівнює s. Складаємо: 0111011 001 = 0111010. Тепер здійснюємо два циклічних зсуву останньої комбінації вправо: після першого вона приймає вигляд 0011101, після другого - 1001110, тобто виходить вже виправлена комбінація. Перевірка показує, що ця комбінація ділиться на Р (Х) без залишку.
1.3 Математична модель
Виходячи з технічного завдання d = 4, а згідно з формулою
d = r + s + 1, де
d - мінімальне кодова відстань;
r - число виявлених помилок;
s - число виправляє помилок.
маємо 2 варіанти:
r = 2, s = 1 - забезпечує виявлення двох помилок і виправлення однієї;
r = 3, s = 0 - забезпечує виявлення потрійних помилок;
Вибираємо варіант 1, так як варіант номер 2 не допустимо по ТЗ (немає виправлення помилок).
Маємо алфавіт в 256 символів, що зажадає 9 розрядів, так як комбінацію 00000000 використовувати не будемо. Маємо k = 9.
Визначено число контрольних символів :
n = k + m
Так як k = 9, то
Тоді для :
n = 9 + 5 = 14
Знайдемо утворює многочлен:
Виберемо з таблиці 1.1. Нехай
1.4 Побудова твірної матриці
З вище отриманих розрахунків ми знаємо, що число інформаційних символів (біт) дорівнює 9. Отже розмірність одиничної матриці буде 9. Число перевірочних символів m = 5, отже отримаємо додаткову матрицю, що має 9 рядків і 5 стовпців.
Знайдемо додаткову матрицю:
100000000 | 100111
100111 |---------------------
----------
00111000111: 1-й залишок
--------
01110001110: 2-й залишок
--------
11100011100: 3-й залишок
100111
-------
11111011111: 4-й залишок
100111
--------
11001011001: 5-й залишок
100111
--------
10101010101: 6-й залишок
100111
--------
0110101101: 7-й залишок
--------
11010011010: 8-й залишок
100111
--------
10011010011: 9-й залишок
100111
--------
000001
Отже, додаткова матриця має вигляд:
m 5
m 4
m 3
m 2
m 1
0
0
1
1
1
0
1
1
1
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
1
1
0
1
0
1
0
1
1
0
1
1
1
0
1
0
1
0
0
1
1
Складемо твірну матрицю:
k 9
k 8
k 7
k 6
k5
k 4
k 3
k 2
k 1
m 5
m 4
m 3
m 2
m 1
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
0
1
Номер такту
Вхід
Стан осередків регістру
X 0
X 1
X 2
X 3
X 4
1
2
3
4
5
6
7
8
9
0
0
0
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
1
0
1
0
0
0
0
0
0
1
1
1
1
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
1
1
1
1
0
0
0
1
0
0
0
0
0
10
11
12
13
14
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
1
0
1
0
1
0
1
0
1
Номер такту
Ділене
Стан осередків дільника
Вага
залишку
X 0
X 1
X 2
X 3
X 4
6
7
8
9
10
11
12
13
14
15
16
17
18
0
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
0 | 0 | 1 | 1 | 1 | 0 | 0 | |||||||
0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
Знаходження всіх комбінацій циклічного коду досягається підсумовуванням за модулем 2 всіляких поєднань рядків твірної матриці.
1.5 Розрахунок достовірності переданих повідомлень
Достовірність - ступінь відповідності прийнятої інформації переданої. Оцінкою достовірності служить ймовірність правильного прийому, що дорівнює відношенню числа правильно прийнятих символів повідомлення до загального числа переданих символів.
1. Для симетричного каналу з незалежними помилками.
Згідно ТЗ, P 10 = P 01 = 0,5.
Для одиночних помилок:
Для двох помилок:
Загальна ймовірність:
Це означає, що на 1000 переданих символів 7 будуть з помилкою. Тоді для 1000 сиволов достовірність буде 993/1000 = 0,993 або 99,3%.
2. Для несиметричного каналу з незалежними помилками.
Згідно ТЗ, P 10 = 0,3
P 01 = 0,7.
Нехай повідомлення буде наступним G = 11001010101011, а викривлене G 1 = 01101010101011.
Загальна ймовірність:
Це означає, що на 1000 переданих символів 2 будуть з помилкою. Тоді для 1000 сиволов достовірність буде 998/1000 = 0,998 або 99,8%.
1.6 Висновки
У цьому розділі били висвітлені теоретичні основи для вирішення технічного завдання. Були описані структура і специфіка циклічних кодів і методів кодування. Таким чином, була підведена база для подальшої реалізації поставленої задачі на мові програмування, а також схемної реалізації.
2. Технічна реалізація кодера, декодера і вирішувачів
2.1 Модульна структура кодера і його робота
Основу кодують пристроїв двійкових циклічних кодів складають регістри зсуву з зворотними зв'язками, що дозволяють здійснювати як множення, так і розподіл многочленів з приведенням коефіцієнтів за модулем 2. Такі регістри також називають багатотактного лінійними переключательние схемами і лінійними кодовими фільтрами Хаффмена. Вони складаються з комірок пам'яті, суматорів за модулем 2 і пристроїв множення на коефіцієнти многочленів множника або дільника. У разі двійкових кодів для множення на коефіцієнт, що дорівнює 1, потрібно тільки наявність зв'язку в схемі. Якщо коефіцієнт дорівнює 0, то зв'язок відсутній. Зрушення інформації в регістрі здійснюється імпульсами, які надходять з генератора просувають імпульсів. На вхід пристроїв надходять лише коефіцієнти многочленів, причому починаючи з коефіцієнта при змінної у старшій ступеня.
Як вказувалося вище, освіта циклічного коду складається з двох операцій: множення комбінації звичайного двійкового коду G (X) на Одночлен X m і подальшого розподілу цього твору на обраний утворює многочлен P (X). Отримані в залишку від ділення контрольні символи приписуються до кодируемой комбінації. Таким чином, кодує пристрій має поєднувати функції множення і ділення.
Розглянемо методику побудови кодує пристрої. Потрібно скласти схему кодує пристрої для многочлена:
P (X) = X 5 + X 2 + X +1.
Схематичне зображення кодує пристрої представлено на малюнку 2.1.
Рис.2.1. Схематичне зображення кодує пристрої
Схема, зображена на рис. 2.1, працює таким чином. У вихідному стані ключ К1 знаходиться в положенні 1, а ключ К2 замкнутий. Всі підлягають кодуванню інформаційні символи, починаючи зі старшого розряду, надходять одночасно на вихід і через суматор на вході в схему кодування. Після того як пройде останній символ k, ключ К1 переключиться в положення 2, а ключ К2 розмикається. Після цього регістр робить m кроків, що дорівнює числу осередків, тобто п'ять кроків. І весь залишок надходить на вихід. Цей залишок являє собою контрольні символи, наступні за інформаційними символами.
Розглянемо докладніше процес кодування комбінації
Процес кодування комбінації G (X) = 000 100 000 за допомогою кодера на малюнку 2.1, а показаний у таблиці 2.1.
У тактах 1-3 на вхід надходять нулі, тому в регістрі нічого не змінюється. Тільки в такті 4 одиниця кодованого записується в осередки X 0, X 1, X 2 і надходить на вихід. У такті 5 на вхід надходить нуль, тому в X 0 надходить 0, і на виході теж 0. З осередків X 0, X 1, X 2 одиниці переміщуються в осередки X 1, X 2, X 3.
Аналогічно і в такті 6, три одиниці переміщуються далі вправо. На такті 7 одиниця з осередку X 4 надходить на суматор за модулем 2 і складається там з 0, що надходять з входу. Тоді, в результаті складання 1 і 0 за модулем 2 виходить 1, яка надходить на інші підсумовуючі елементи за модулем 2. У результаті у всіх осередках будуть записані 1. У тактах 7, 8, 9 просходит аналогічно такту 6.
Таблиця 2.1. Освіта циклічного коду
Після такту 9 залишок R (X) виявляється записаним в осередках регістру. Після перемикання ключа K1 в положення 2 і вимикання ключа K 2 цей залишок у наступні чотири такту переписується на вихід слідом за інформаційними символами.
2.2 Модульна структура декодера і його робота
Декодування циклічного-коду з виявленням і виправленням декількох помилок. Метод такого декодування був викладений в теоретичному введенні. Розглянемо тепер схемну реалізацію декодування комбінації 10000000010011, спотворену одним символом і прийняла вигляд 10010000010011. Декодер (рис.2.2) складається з дільника, виконаного для поділу на многочлен P (X) = X 5 + X 2 + X +1, і запам'ятовуючого пристрою, що представляє собою регістр з суматором символів k. Комбінація поступає одночасно на дільник і запам'ятовуючий пристрій починаючи зі старшого розряду. Спотворений символ в комбінації відзначений почерківаніем. Спочатку ключ K1 замкнутий, а ключ К2 розімкнутий. У таблиці 2.2 показано процес поділу починаючи з такту 6, тому що в перші п'ять тактів відбувається заповнення дільника і зворотний зв'язок ще не виявляється.
Рис. 2.2. Сруктурной схема декодування циклічного коду з виправленням однієї помилки.
У такті 6 одиниця з Х4 надходить на суматори за модулем 2, і в X 0 записується одиниця, нуль, який перебував у X 0, що склався з одиницею дасть 1 і вона запишеться у X 1, одиниця з X 1 склавшись з 1 дасть нуль і цей нуль запишеться в X 2, нуль з X 2 перейде в X 3, а одиниця з X 3 в X 4. Далі аналогічно.
Таблиця 2.2. Робота дільника
0
1
1
1
1
0
0
1
1
0